<?php
/**
 * @title 1621. 大小为 K 的不重叠线段的数目 - 迭代
 * @author start2004
 */

// ini_set("memory_limit", "128M");

// class Solution {
//
//     function find() {
//
//     }
// }


class Solution {

    /**
     * @param Integer $n
     * @param Integer $k
     * @return Integer
     */
    function numberOfSets($n, $k) {
        /**
         * @since 2020-10-19 缓存
         */
        $dps = [];

        /**
         * @since 2020-10-19 取模
         */
        $mod = pow(10,9)+7;

        /**
         * @since 2020-10-19 1个区间段, 在总长度 `l` 下的可能性
         */
        for($l=1; $l<=$n-$k; $l++){
            $sum = ($l*($l+1))>>1;
            $dps[1][$l] = $sum % $mod;
        }
        // return $dps;

        /**
         * @since 2020-10-19 依次增加区间段数量 `i`
         */
        $l++;
        for($i=2; $i<=$k-1; $i++){
            /**
             * @since 2020-10-19 i个区间段的总长度范围 `j`
             */
            for($j=$i; $j<=($n-1) - ($k-$i);$j++){
                /**
                 * @since 2020-10-19 第`2-i`区间的总长度范围, `i-1` 到 `j-1`
                 */
                $sum = 0;
                for($m=$i-1; $m<=$j-1; $m++){
                    $sum += ($j-$m) * $dps[$i-1][$m];
                }

                /**
                 * @since 2020-10-19 i个区间段, 在总长度j, 组成方案数
                 */
                $dps[$i][$j] = $sum % $mod;
                // echo "区间段数量={$i}, 总长度={$j}, 方案={$sum}", PHP_EOL;
            }

            $l++;
        }

        /**
         * @since 2020-10-20 k个区间数
         */
        if($k == 1){
            $sum = $dps[1][$n-1];
        } else {
            $j = $n-1;
            $sum = 0;
            for($m = $k-1; $m <= $j-1; $m++){
                $sum += ($j-$m) * $dps[$k-1][$m];
            }
            $sum = $sum % $mod;
        }

        /**
         * @return
         */
        return $sum;
    }
}


/**
 * @url http://127.0.0.1/leetcode/202010/2020.10.17_4.php
 */
$datas = [
    [5,1], // 10
    [5,2], // 15
    [5,3], // 7
    [5,4], // 1
    // [4,2], // 5
    // [3,1], // 3
    // [30,7], // 796297179
    // [5,3], // 7
    // [3,2], // 1
    // [6,4], // 9
    // [633, 64], // 690240372
    // [1000, 500], //
];

include_once dirname(__DIR__) . DIRECTORY_SEPARATOR ."xhprof.php";
$xhprof = new Xhprof();
foreach ($datas as $data){
    var_dump($data);

    $obj = new Solution();
    $result = $obj->numberOfSets(...$data);
    // $result = $obj->($xhprof->tree($data));
    // $result = $obj->($xhprof->listNode($data));
    // $result = $obj->find(...$data);
    var_dump($result);
    // if(count($result)<=20){
    //     var_dump($result);
    // } else {
    //     var_dump(count($result));
    // }
    echo str_repeat(PHP_EOL, 3);
    echo str_repeat("<br>", 3);
}

// foreach ($datas as $data){
//     $obj = new $data[0][0](...$data[1][0]);
//
//     for ($i=1; $i<count($data[0]); $i++){
//         $result = $obj->$data[0][$i](...$data[1][$i]);
//
//         echo $data[0][$i] ."(\"". implode(",", $data[1][$i]) ."\") ";
//             if($result === true){
//                 echo "True";
//             } elseif($result === false) {
//                 echo "False";
//             } elseif($result === null) {
//                 echo "Null";
//             } elseif(is_array($result)) {
//                 var_dump($result);
//             } else {
//                 echo $result;
//             }
//         echo PHP_EOL;
//     }
//
//     echo str_repeat(PHP_EOL, 3);
// }
$xhprof->end();
